package J20250121_Dynamic;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划27——30
 * User: 王圆豪
 * Date: 2025-01-22
 * Time: 15:19
 */
public class Solution2 {
    //最长递增子序列——https://leetcode.cn/problems/longest-increasing-subsequence/submissions/594736358/
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ret = 1;
        for(int i = 0;i<n;i++) dp[i] = 1;
        for(int i = 1; i < n; i++){
            int max = 0;
            for(int j = i; j >= 0; j--){
                if(nums[i] > nums[j]){
                    max = Math.max(dp[j], max);
                }
            }
            dp[i] += max;
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    //摆动序列——https://leetcode.cn/problems/wiggle-subsequence/description/
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 0; i < n; i++) f[i] = g[i] = 1;
        int ret = 1;
        for(int i = 1;i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    f[i] = Math.max(f[i],g[j]+1);
                }
                else if(nums[i] < nums[j]){
                    g[i] = Math.max(g[i],f[j]+1);
                }
            }
            ret = Math.max(Math.max(f[i],g[i]),ret);
        }
        return ret;
    }

    //最长递增子序列的个数——https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) dp[i] = arr[i] = 1;
        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = i; j>=0;j--){
                if(nums[i] > nums[j]){
                    int a = dp[i],b = dp[j]+1;
                    if(a == b) arr[i]+=arr[j];
                    else if(a < b) arr[i] = arr[j];
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        int count = 0;
        for(int i = 0 ; i < n;i++){
            if(dp[i] == ret) count += arr[i];
        }
        return count;
    }

    //最长数对链——https://leetcode.cn/problems/maximum-length-of-pair-chain/
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b)->a[0]-b[0]);
        int m = pairs.length,n = pairs[0].length;
        int[] dp = new int[m];
        for(int i = 0; i < m; i++) dp[i]++;
        int ret = 1;
        for(int i = 1; i < m; i++){
            for(int j = 0; j < i; j++){
                int a = pairs[i][0], b = pairs[j][1];
                if(a > b){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}
